{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Consecutive Ones III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestOnes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大连续1的个数 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二进制数组&nbsp;<code>nums</code>&nbsp;和一个整数 <code>k</code>，如果可以翻转最多 <code>k</code> 个 <code>0</code> ，则返回 <em>数组中连续 <code>1</code> 的最大个数</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>[1,1,1,0,0,<strong>1</strong>,1,1,1,1,<strong>1</strong>]\n",
    "粗体数字从 0 翻转到 1，最长的子数组长度为 6。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>[0,0,1,1,<strong>1</strong>,<strong>1</strong>,1,1,1,<strong>1</strong>,1,1,0,0,0,1,1,1,1]\n",
    "粗体数字从 0 翻转到 1，最长的子数组长度为 10。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums[i]</code>&nbsp;不是&nbsp;<code>0</code>&nbsp;就是&nbsp;<code>1</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-consecutive-ones-iii](https://leetcode.cn/problems/max-consecutive-ones-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-consecutive-ones-iii](https://leetcode.cn/problems/max-consecutive-ones-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,0,0,0,1,1,1,1,0]\\n2', '[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        left,right = 0,0 \n",
    "        ans = 0\n",
    "        \n",
    "        while right < len(A):\n",
    "            if A[right]==0:\n",
    "                K-=1\n",
    "            right+=1\n",
    "            while K<0:\n",
    "                if A[left]==0:\n",
    "                    K+=1\n",
    "                left+=1\n",
    "            ans = max(ans,right-left)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        i = 0\n",
    "        for j in range(len(A)):\n",
    "            K -= 1 - A[j]\n",
    "            if K < 0:\n",
    "                K += 1 - A[i]\n",
    "                i += 1\n",
    "        return j - i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode-cn.com/problems/max-consecutive-ones-iii/\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        if sum(A) + K >= len(A):\n",
    "            return len(A)\n",
    "        current_term = 1\n",
    "        current_counting = 0\n",
    "        counting_res = []\n",
    "        for i in A:\n",
    "            if i == current_term:\n",
    "                current_counting += 1\n",
    "            else:\n",
    "                counting_res.append(current_counting)\n",
    "                current_term = 1 - current_term\n",
    "                current_counting = 1\n",
    "        counting_res.append(current_counting)\n",
    "        if K == 0:\n",
    "            return max(counting_res[::2])\n",
    "        res = 0\n",
    "\n",
    "        def max_turning_range(start_pos, total):\n",
    "            zero_list = counting_res[1::2]\n",
    "            start_pos = start_pos // 2\n",
    "            end_pos = start_pos\n",
    "            remaining = total\n",
    "            while True:\n",
    "                if end_pos >= len(zero_list):\n",
    "                    return -3, remaining\n",
    "                elif remaining < zero_list[end_pos]:\n",
    "                    return 2 * end_pos - 1, remaining\n",
    "                else:\n",
    "                    remaining -= zero_list[end_pos]\n",
    "                    end_pos += 1\n",
    "\n",
    "        for i in range(1, len(counting_res), 2):\n",
    "            if counting_res[i] > K:\n",
    "                res = max(res, K + max(counting_res[i - 1], counting_res[i + 1]))\n",
    "            else:\n",
    "                end_point, remaining_k = max_turning_range(i, K)\n",
    "                if end_point < 0:\n",
    "                    new_res = sum(counting_res[i - 1:]) + remaining_k\n",
    "                    res = max(res, new_res)\n",
    "                    break\n",
    "                else:\n",
    "                    new_res = sum(counting_res[i - 1:end_point + 2]) + remaining_k\n",
    "                    res = max(res, new_res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        N = len(A)\n",
    "        l = 0\n",
    "        r = 0\n",
    "        count = 0\n",
    "        result = 0\n",
    "        while r < N:\n",
    "            count += 1 if A[r] == 0 else 0\n",
    "            while count > K:\n",
    "                count -= 1 if A[l] == 0 else 0\n",
    "                l += 1\n",
    "            \n",
    "            result = max(result, r-l+1)\n",
    "            r += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        i = 0\n",
    "\n",
    "        for j in range(len(A)):\n",
    "            K -= 1 - A[j]\n",
    "            if K < 0:\n",
    "                K += 1 - A[i]\n",
    "                i += 1\n",
    "        return j - i + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        n = len(A)\n",
    "        if n < 3:\n",
    "            return min(n, sum(A)+K)\n",
    "        cnt = 0\n",
    "        opt = 0\n",
    "        start_idx = 0\n",
    "        for idx, num in enumerate(A):\n",
    "            if num == 0:\n",
    "                cnt += 1\n",
    "            # to validate the window\n",
    "            while cnt > K:\n",
    "                if A[start_idx] == 0:\n",
    "                    cnt -= 1\n",
    "                start_idx += 1\n",
    "            opt = max(opt, idx-start_idx+1)\n",
    "        return opt\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        start, end = 0, 0\n",
    "        count = 0\n",
    "        result = 0\n",
    "        n = len(A)\n",
    "        while end < n:\n",
    "            count += A[end] == 0\n",
    "            while count > K:\n",
    "                count -= A[start] == 0\n",
    "                start += 1\n",
    "            result = max(result, end - start + 1)\n",
    "            end += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        if not A:\n",
    "            return 0\n",
    "        \n",
    "        left, right = 0, 0 \n",
    "        max_len = 0\n",
    "        a_len = len(A)\n",
    "        \n",
    "        temp_k = 0\n",
    "        while right < a_len:\n",
    "            # 窗口右滑动\n",
    "            if A[right] == 1 or temp_k < K:\n",
    "                max_len = max(max_len, right - left + 1)\n",
    "                if A[right] == 0:\n",
    "                    temp_k += 1\n",
    "                right += 1\n",
    "                continue\n",
    "\n",
    "            # 窗口左移动\n",
    "            \n",
    "            if left == right:\n",
    "                left += 1\n",
    "                right += 1\n",
    "            else:\n",
    "                if A[left] == 0:\n",
    "                    temp_k -= 1\n",
    "                    \n",
    "                left += 1\n",
    "                \n",
    "            \n",
    "            \n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A, K: int) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        count = 0\n",
    "        for right in range(len(A)):\n",
    "            if A[right] == 0:\n",
    "                count += 1\n",
    "            if count > K:\n",
    "                if A[left] == 0:\n",
    "                    count -= 1\n",
    "                left += 1\n",
    "        return right - left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        result = 0 # 仅含1的最长子串\n",
    "        len_0 = 0 # 子串内0的数量\n",
    "        zc = [] # 子串\n",
    "        for i in range(len(A)):\n",
    "            zc.append(A[i])\n",
    "            if A[i] == 0:\n",
    "                len_0 += 1\n",
    "            while len_0 > K:\n",
    "                if zc[0] == 0:\n",
    "                    len_0 -= 1\n",
    "                zc = zc[1::]\n",
    "            if result < len(zc):\n",
    "                result = len(zc)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        count = collections.Counter(A)\n",
    "        if K > count[0]:\n",
    "            return len(A)\n",
    "        else:\n",
    "            return self.atMostK(A,K)\n",
    "\n",
    "    def atMostK(self, A, k):\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i in range(len(A)):\n",
    "            if A[i] == 0:\n",
    "                k -= 1\n",
    "            while k < 0:\n",
    "                print(i,j)\n",
    "                ans = max(ans,i - j)\n",
    "                if A[j] == 0:\n",
    "                    k += 1\n",
    "                j += 1\n",
    "            ans = max(ans,i - j + 1)\n",
    "            \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, A: List[int], K: int) -> int:\n",
    "        tol = [0]\n",
    "        for x in A:\n",
    "            tol.append(tol[-1] + x)\n",
    "        start = 0\n",
    "        cur_len = 0\n",
    "        res = 0\n",
    "        while start + cur_len < len(tol):\n",
    "            cur_val = tol[start + cur_len] - tol[start]\n",
    "            if cur_val + K >= cur_len:\n",
    "                res = cur_len\n",
    "                cur_len += 1\n",
    "            else:\n",
    "                start += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, nums: List[int], k: int) -> int:\n",
    "        que, ret = [], 0\n",
    "        count = k\n",
    "        for num in nums:\n",
    "            que.append(num)\n",
    "            if num == 0:\n",
    "                count -= 1\n",
    "            while count < 0:\n",
    "                if que and que.pop(0) == 0:\n",
    "                    count += 1\n",
    "            ret = max(ret, len(que))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, nums: List[int], k: int) -> int:\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "        zero_num = 0\n",
    "\n",
    "        for right, x in enumerate(nums):\n",
    "            if x == 0:\n",
    "                zero_num += 1\n",
    "            while zero_num > k:\n",
    "                if nums[left] == 0:\n",
    "                    zero_num -= 1\n",
    "                left += 1\n",
    "            max_len = max(max_len, right-left+1)\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, nums: List[int], k: int) -> int:\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "\n",
    "        for p2 in range(len(nums)):\n",
    "            k = k - (1 - nums[p2])             \n",
    "            if k < 0:               \n",
    "                k = 1 - nums[p1] + k   \n",
    "                p1 += 1\n",
    "\n",
    "        return p2 - p1 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, nums: List[int], k: int) -> int:\n",
    "        num0 = nums.count(0)\n",
    "        n = len(nums)\n",
    "        if num0 <= k:\n",
    "            return n\n",
    "        maxnum = left = right = counter0 = 0\n",
    "        temp = 1\n",
    "        if nums[0] == 0:\n",
    "            counter0 += 1\n",
    "        while left < n and right < n:\n",
    "            if counter0 > k:\n",
    "                left += 1\n",
    "                temp -= 1\n",
    "                if nums[left-1] == 0:\n",
    "                    counter0 -= 1\n",
    "            else:\n",
    "                right += 1\n",
    "                temp += 1\n",
    "                if right < n and nums[right] == 0:\n",
    "                    counter0 += 1\n",
    "                if right < n and counter0 <= k and temp > maxnum:\n",
    "                    maxnum = temp\n",
    "        return maxnum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, nums:List[int], k: int) -> int:\n",
    "        slow, fast = 0, 0\n",
    "        result = 0\n",
    "        while fast < len(nums):\n",
    "            if nums[fast] == 1:\n",
    "                fast += 1\n",
    "            elif nums[fast] == 0 and k > 0:\n",
    "                fast += 1\n",
    "                k -= 1\n",
    "            elif nums[slow]==0 and nums[fast]==0 and k==0:\n",
    "                slow += 1\n",
    "                fast += 1\n",
    "            elif nums[fast] == 0 and k == 0:\n",
    "                result = max(result, (fast - slow))\n",
    "                if nums[slow] == 0:\n",
    "                    k += 1\n",
    "                slow += 1\n",
    "        else:\n",
    "            result = max(result, fast-slow)\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, nums: List[int], k: int) -> int:\n",
    "        #滑窗\n",
    "        zero = []\n",
    "        n = len(nums)\n",
    "        left = -1\n",
    "        res = 0\n",
    "        cnt1 = 0\n",
    "        cnt0 = 0\n",
    "        for i in range(n):\n",
    "            if nums[i]==1:\n",
    "                cnt1 += 1\n",
    "            else:\n",
    "                zero.append(i)\n",
    "                cnt0 += 1\n",
    "            if cnt0 > k:\n",
    "                left += 1\n",
    "                cnt0 -= 1\n",
    "            if left!=-1:\n",
    "                res = max(res,i-zero[left])\n",
    "            else:\n",
    "                res = i + 1  \n",
    "        return res\n",
    "\n",
    "\n",
    "        # cur = 0\n",
    "        # res = 0\n",
    "        # remain = k\n",
    "        # cnt = 0\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i] == 1:\n",
    "        #         cur += 1\n",
    "        #         cnt += 1\n",
    "        #     else:\n",
    "        #         remain -= 1\n",
    "        #         if remain==k-1:\n",
    "        #             cur += 1\n",
    "        #             cnt = 0\n",
    "        #         elif remain!=0:\n",
    "        #             cnt += 1\n",
    "        #             cur += 1\n",
    "        #         else:\n",
    "        #             cur = cnt + 1\n",
    "        #             remain = k\n",
    "        #     print(i,cur,cnt,remain)\n",
    "        #     res = max(res,cur)\n",
    "        # return res\n",
    "                    \n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, nums: List[int], k: int) -> int:\n",
    "        #0的数量大于k的时候，就可以走了 。\n",
    "        res ,dic = 0, {}\n",
    "        \n",
    "        start = 0\n",
    "        for end in range(len(nums)):\n",
    "            dic[nums[end]] = dic.get(nums[end],0) +1\n",
    "            if dic.get(0,0) <= k:\n",
    "                res = max(res, end-start +1)\n",
    "            #print(end,dic,res)\n",
    "            while dic.get(0,0) > k:\n",
    "                dic[nums[start]] -= 1\n",
    "                start += 1\n",
    "\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, nums: List[int], k: int) -> int:\n",
    "        left, right = 0, 0\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        while right < n:\n",
    "            if nums[right] == 0:\n",
    "                k -= 1\n",
    "            while k < 0:\n",
    "                if nums[left] == 0:\n",
    "                    k += 1\n",
    "                left += 1\n",
    "            res = max(res, right-left+1)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, nums: List[int], k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        length = len(nums)\n",
    "        count = 0\n",
    "        res = 0\n",
    "        while r < length:\n",
    "            if nums[r] == 0:\n",
    "                count += 1\n",
    "            while count > k:\n",
    "                if nums[l] == 0:\n",
    "                    count -= 1\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "            r += 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestOnes(self, nums, k):\n",
    "        if k==0:\n",
    "            left=0\n",
    "            right=0\n",
    "            ind=False\n",
    "            i=0\n",
    "            count=0\n",
    "            while i<len(nums) and ind==False:\n",
    "                if nums[i]==0:\n",
    "                    i+=1\n",
    "                else:\n",
    "                    ind=True\n",
    "                    left=i\n",
    "                    right=i\n",
    "            if ind==False:\n",
    "                return count\n",
    "            else:\n",
    "                count=1\n",
    "            while right<len(nums)-1:\n",
    "                if nums[right+1]==1:\n",
    "                    right+=1\n",
    "                    count=max(count,right-left+1)\n",
    "                else:\n",
    "                    right+=1\n",
    "                    while nums[right]==0 and right<len(nums)-1:\n",
    "                        right+=1\n",
    "                    left=right\n",
    "            return count\n",
    "        if len(nums)==1:\n",
    "            if nums[0]==1:\n",
    "                return 1\n",
    "            else:\n",
    "                if k>=1:\n",
    "                    return 1\n",
    "        left=0\n",
    "        right=0\n",
    "        count=0\n",
    "        cur=0\n",
    "        if nums[0]==0:\n",
    "            cur+=1\n",
    "        while right<len(nums)-1:\n",
    "            if cur<k and nums[right+1]==1:\n",
    "                right+=1\n",
    "                count=max(count,right-left+1)\n",
    "            elif cur<k and nums[right+1]==0:\n",
    "                right+=1\n",
    "                cur+=1\n",
    "                count=max(count,right-left+1)\n",
    "            elif cur==k and nums[right+1]==1:\n",
    "                right+=1\n",
    "                count=max(count,right-left+1)\n",
    "            elif cur==k and nums[right+1]==0:\n",
    "                while left<right and cur==k:\n",
    "                    if nums[left]==1 and nums[left+1]==1:\n",
    "                        left+=1\n",
    "                        count=max(count,right-left+1)\n",
    "                    elif nums[left]==1 and nums[left+1]==0:\n",
    "                        left+=1\n",
    "                        count=max(count,right-left+1)\n",
    "                    elif nums[left]==0 and nums[left+1]==1:\n",
    "                        left+=1\n",
    "                        cur-=1\n",
    "                        count=max(count,right-left+1)\n",
    "                    elif nums[left]==0 and nums[left+1]==0:\n",
    "                        left+=1\n",
    "                        cur-=1\n",
    "                        count=max(count,right-left+1)\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestOnes(self, nums: list[int], k: int) -> int:\n",
    "        ln = len(nums)\n",
    "        # 直接找出所有value为0的index，加上两端作为起终点\n",
    "        nums = [-1] + [i for i, num in enumerate(nums) if num == 0] + [ln]\n",
    "        k += 1\n",
    "        ln1 = len(nums) - k\n",
    "        # 相差k+1(即相隔k)的两个index的value(即原index)之差再-1即为即为中间能包含的连续为1的数,这里的k已经是k+1了\n",
    "        return ln if ln1 <= 1 else max(nums[i + k] - nums[i] for i in range(ln1)) - 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
